package com.s11.heap;

import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.Queue;

public class MinHeap {

	/**
	 * 堆中已经存储的数据个数
	 */
	private int count;

	private Integer[] arr;

	public MinHeap(int length) {
		this.count = 0;
		this.arr = new Integer[length + 1];
	}

	/**
	 * 堆可以存储的最大数据个数
	 */
	public int getLength() {
		return this.arr.length - 1;
	}

	// 策略一：只有队伍未满的时候再插入
	public void insert(int data) {
		if (this.count < this.getLength()) {
			this.arr[++this.count] = data;
			int i = this.count;
			// 当不满足父节点 小于等于 叶子节点
			while (i / 2 > 0 && arr[i / 2] > arr[i]) {
				// 自下往上堆化
				swap(this.arr, i / 2, i);
				i /= 2;
			}
		}
	}

	// 策略二：即使队伍满则进行比较，如果大于堆顶元素则进行下沉
	public void insert2(int data) {
		if (this.count < this.getLength()) {
			this.insert(data);
		} else {
			Integer topData = this.arr[1];
			if (data > topData) {
				this.arr[1] = data;
				heapify(this.arr, 1, this.count);
			}
		}
	}

	public void removeTop() {
		if (this.count > 0) {
			// 最后一位覆盖顶部
			this.arr[1] = this.arr[this.count];
			this.arr[this.count] = null;
			this.count--;
			heapify(this.arr, 1, this.count);
		}
	}
	
	public Integer getTop() {
		if (this.count > 0) {
			return this.arr[1];
		}
		return null;
	}
	
	/**
	 * 堆排序
	 */
	public static void sort(Integer[] arr) {
		// 建堆
		buildHeap(arr);

		// 排序
        int i = arr.length;
		while (i > 1) {
			 // 将堆顶元素（最大）与最后一个元素交换位置			
			swap(arr, 1, i);
			// 完成堆化 和 顶部元素为最大
			heapify(arr, 1, --i);
		}
	}

	/**
	 * top k
	 * @return 
	 */
	public static int topK(int[] arr, int k) {
		Queue<Integer> queue = new PriorityQueue<>();
		for (int num : arr) {
			if (queue.size() < k) {
				queue.add(num);
			} else if (queue.element() < num) {
				queue.remove();
				queue.add(num);
			}
		}
		return queue.element();
	}
	
	public void clear() {
		for (int i = 1; i < this.arr.length; i++) {
			this.arr[i] = null;
		}
	}

	@Override
	public String toString() {
		return Arrays.toString(this.arr);
	}

	/**
	 * 也就是最后一个非叶子节点，依次堆化直到根节点
	 * 
	 * @param n
	 *            需要堆化元素的个数
	 */
	private static void buildHeap(Integer[] arr) {
		// 每个数据从上到下的堆化
		for (int i = arr.length >>> 1; i > 0; i--) {
			heapify(arr, i, arr.length);
		}
	}

	private static void swap(Integer[] arr, int i, int j) {
		if (i != j) {
			int temp = arr[i];
			arr[i] = arr[j];
			arr[j] = temp;
		}
	}

	/**
	 * 对下标为 i 进行从上到下堆化，范围为到 n
	 * 
	 * @param i
	 *            指定下标
	 * @param n
	 *            范围
	 */
	private static void heapify(Integer[] arr, int i, int n) {
		while (true) {
			int minPosi = i;
			minPosi = (i * 2 <= n && arr[minPosi] > arr[i * 2]) ? i * 2
					: minPosi;
			minPosi = (i * 2 + 1 <= n && arr[minPosi] > arr[i * 2 + 1]) ? i * 2 + 1
					: minPosi;
			if (i == minPosi) {
				break;
			}
			swap(arr, minPosi, i);
			i = minPosi;
		}
	}

}
